﻿//456. 132 模式
//给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，
//并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
//如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。


class Solution {
public:
    bool find132pattern(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> left(n);
        int left_min = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            left[i] = left_min;
            left_min = min(left_min, nums[i]);
        }
        stack<int> sta;
        for (int i = n - 1; i > 0; i--)
        {
            //单调递减栈
            while (!sta.empty() && sta.top() < nums[i])
            {
                if (sta.top() > left[i])
                    return true;
                sta.pop();
            }
            sta.push(nums[i]);
        }
        return false;
    }
};